package example;

import java.util.Arrays;

public class Merge {

    private Merge() {
    }

    // 归并排序
    public static <E extends Comparable<E>> void sort(E[] data) {
        sort(data, 0, data.length - 1);
    }

    public static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2; //
        sort(data, l, mid);
        sort(data, mid + 1, r);
        merge(data, l, mid, r);
    }

    // 归并排序v2
    public static <E extends Comparable<E>> void sort2(E[] data) {
        sort2(data, 0, data.length - 1);
    }

    public static <E extends Comparable<E>> void sort2(E[] data, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2; //
        sort2(data, l, mid);
        sort2(data, mid + 1, r);
        // 优化, 如果数组已经有序, 不需要再执行下一轮归并
        if (data[mid].compareTo(data[mid + 1]) >= 0)
            merge(data, l, mid, r);
    }

    // 归并排序v3
    public static <E extends Comparable<E>> void sort3(E[] data) {
        sort3(data, 0, data.length - 1);
    }

    // TODO 使用插入排序优化归并排序
    public static <E extends Comparable<E>> void sort3(E[] data, int l, int r) {
        if (r - l <= 15) {
            Insertion.sort(data, l, r);
            return;
        }
        int mid = l + (r - l) / 2; //
        sort3(data, l, mid);
        sort3(data, mid + 1, r);
        if (data[mid].compareTo(data[mid + 1]) >= 0)
            merge(data, l, mid, r);
    }

    // 归并过程
    public static <E extends Comparable<E>> void merge(E[] data, int l, int mid, int r) {
        E[] dup = Arrays.copyOfRange(data, l, r + 1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) { // 取右半边值
                data[k] = dup[j - l];
                j++;
            } else if (j > r) {   // 取左半边值
                data[k] = dup[i - l];
                i++;
            } else if (dup[i - l].compareTo(dup[j - l]) <= 0) { // 取左半边值
                data[k] = dup[i - l];
                i++;
            } else { // 取右半边值
                data[k] = dup[j - l];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        for (int n : new int[]{10_0000, 100_0000, 1000_0000}) {
            Integer[] data = Utils.randomArray(n,n);
            Integer[] data1 = Arrays.copyOf(data, data.length);
            System.out.println("无序数据样本:");
            Utils.timeSpent(Merge::sort, "归并排序V1", data, 0, data.length - 1);
            Utils.timeSpent(Merge::sort2, "归并排序V2", data1, 0, data1.length - 1);

            System.out.println("有序数据样本:");
            Integer[] data2 = Utils.orderedArray(n);
            Integer[] data22 = Arrays.copyOf(data2, data2.length);
            Utils.timeSpent(Merge::sort, "归并排序V1", data2, 0, data2.length - 1);
            Utils.timeSpent(Merge::sort2, "归并排序V2", data22, 0, data22.length - 1);


        }
    }


}
